﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<unordered_map>
#include<algorithm>
using namespace std;
//P1102 排序对结果无影响 可以先排序优化再做处理 
//注意sort upper_bound lower_bound的使用方式
//const int N = 2e5 + 10;
//typedef long long int LL;
//LL a[N];
//int n, c;
//int main()
//{
//	cin >> n >> c;
//	for (int i = 1; i <= n; i++)
//		cin >> a[i];
//	sort(a + 1, a + 1 + n);
//	int ret = 0;
//	for (int i = 2; i <= n; i++)//从2开始往前找 因为b=a[i]-c c>0 所以b<a 
//	{
//		LL b = a[i] - c;//往前找可以避免重复 同时利用排序的有序性 减少计算量
//		ret += upper_bound(a+1,a+i,b)-lower_bound(a + 1, a + i, b);
//	}//upper_bound lower_bound 是左闭右开 实际访问区间为[a+1,a+i-1]
//	cout << ret << endl;
//	return 0;
//}
//NC235558 在有序数组中 通过二分查找 得到一段符合条件的数据
//在本题中 体现为找到大于等于x的下标 以及小于等于y的下标
//结合线段来写二分查找模板 化为两段
//const int N = 1e5 + 10;
//int a[N];
//int check(int x, int y,int n)
//{
//	//找到大于等于x的元素的下标
//	int left = 1, right = n;
//	while (left < right)
//	{
//		int mid = (left + right) / 2;
//		if (a[mid] >= x) right = mid;//条件要画图思考 不然容易写反进死循环
//		else left = mid+1;
//	}
//	if (a[left] < x)return 0;//可能没有这个区间 直接返回0即可
//	int ret_l = left;
//	//找到小于等于y的元素下标 
//	left = 1; right = n;
//	while (left < right)
//	{
//		int mid = (left + right + 1) / 2;
//		if (a[mid] <= y)left = mid;
//		else right = mid - 1;
//	}
//	if (a[left] > y) return 0;
//	return left - ret_l + 1;
//}
//int main()
//{
//	int n; cin >> n;
//	for (int i = 1; i <= n; i++)cin >> a[i];
//	int q; cin >> q;
//	while (q--)
//	{
//		int x, y; cin >> x >> y;
//		cout << check(x, y, n) << endl;
//	}
//	return 0;
//}

//系统自带二分查找 但建议用模板自己写 
//<algorithm> lower_bound >= upper_bound >
//使用条件：结果分段情况下使用 
//二分算法 算法结束后要检查结果是否争取 查找结果为left=right指向目标下标
//算法模板：
//⼆分查找区间左端点
//int l = 1, r = n;//节点从1开始 可以自己改为0与n-1；
//while (l < r)
//{
//	int mid = (l + r) / 2;
//	if (check(mid)) r = mid;//结合图形 
//	else l = mid + 1;//+1是确定mid指向的地方没有目标 即不包含=
//}
//⼆分查找区间右端点
//int l = 1, r = n;
//while (l < r)
//{
//	int mid = (l + r + 1) / 2;//右端点求中点时要加一
//	if (check(mid)) l = mid;
//	else r = mid - 1;
//}
//leetcode 二分模板题 34. 在排序数组中查找元素的第一个和最后一个位置
//class Solution {
//public:
//    vector<int> searchRange(vector<int>& nums, int target) {
//        int n = nums.size();
//        if (n == 0)return{ -1,-1 };
//        int left = 0, right = n - 1;
//        while (left < right)
//        {
//            int mid = (right + left) / 2;
//            if (nums[mid] >= target)right = mid;
//            else left = mid + 1;
//        }
//        if (nums[left] != target)return{ -1,-1 };
//        int ret_l = left;
//        left = 0, right = n - 1;
//        while (left < right)
//        {
//            int mid = (right + left + 1) / 2;
//            if (nums[mid] > target)right = mid - 1;
//            else left = mid;
//        }
//        if (nums[left] != target)return{ -1,-1 };
//        return { ret_l,left };
//    }
//};
//防止溢出 （l+r+1)/2--> l+(r-l+1)/2
//NC207040 丢手绢 找到环内最远距离 
//处理分为顺时针与逆时针，因此找到中间点sum/2为判断条件 
//不论区间是否合法 都需要更新结果 暴力模拟的过程也需要仔细研究 值得再做一次
//const int N = 1e5 + 10;
//typedef long long int LL;
//int a[N];
//int main()
//{
//	int n; cin >> n;
//	LL sum = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i]; sum += a[i];
//	}
//	int left = 1, right = 1; LL k = 0;
//	LL ret = 0;
//	while (right <= n)
//	{
//		k += a[right];//进窗口
//		while (2 * k >= sum)
//		{
//			ret = max(ret, sum - k);//不合法窗口 此时逆时针小于顺时针
//			k -= a[left++];//出窗口
//		}
//		ret = max(ret, k);//合法窗口 此时顺时针小于逆时针
//		right++;
//	}
//	cout << ret << endl;
//	return 0;
//}

//NC18386 子串
//和上题同理 滑动窗口 解决连续区间问题
//int kind;
//int mp[200];//充当哈希表
//int main()
//{
//	string s; cin >> s;
//	int n = s.size();
//	int left = 0, right = 0;
//	int ret = n;//初始化
//	while (right < n)
//	{
//		if (++mp[s[right]] == 1)kind++;//进窗口
//		while (kind == 26)
//		{
//			ret = min(ret, right - left + 1);//窗口合法 更新结果
//			if (--mp[s[left++]] == 0)kind--;//出窗口
//		}
//		right++;
//	}
//	cout << ret << endl;
//	return 0;
//}
// 
//P1638 逛画展 滑动窗口题 
//const int N = 1e6 + 10;
//int a[N];
//int main()
//{
//	int n, m; cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//		cin >> a[i];
//	//保证有解 找到合法区间 取最小长度 
//	//找区间过程 指针不必回退 使用窗口即可 
//	//初始化
//	int left = 1, right = 1; int ret_l, ret_r; int ret = 0x3f3f3f3f;
//	unordered_map<int, int> mp;//使用hash来维护数据 记录相应画家出现次数
//	while (right <= n)
//	{
//		mp[a[right]]++;//right指向数据进入窗口
//		while (mp.size() == m)//判断是否合法
//		{
//			int len = right - left + 1;
//			if (len < ret)//合法时更新数据 右左往右读取数据 输出ret_l小的区间
//			{
//				ret = len; ret_l = left; ret_r = right;
//			}
//			if (--mp[a[left]] == 0)mp.erase(a[left]);//出窗口
//			left++;
//		}
//		right++;
//	}
//	cout << ret_l << " " << ret_r << endl;
//	return 0;
//}
//UVA11572 唯一的雪花 滑动窗口模板题 同向双指针
//滑动窗口的核心在于规避了不必要的操作 指针不回退
//由暴力遍历得来 找到遍历规律后 再采用滑动窗口来做
//1.初始化 用什么结构来维护数据 2.进窗口 3.判断 4.出窗口 5.更新结果
//const int N = 1e6 + 10;
//int a[N];
//int main()
//{
//	int T; cin >> T;
//	while (T--)
//	{
//		int n; cin >> n;
//		for (int i = 1; i <= n; i++)
//			cin >> a[i];
//		//初始化
//		unordered_map<int, int> mp;//维护窗口内元素的出现次数
//		int left = 1, right = 1;
//		int ret = 0;
//		while (right <= n)
//		{
//			mp[a[right]]++;//入窗口
//			
//			while (mp[a[right]] > 1)//判断
//			{
//				mp[a[left++]]--;//出窗口
//			}
//			ret = max(right - left + 1, ret);//窗口合法 更新结果 
//			right++;
//		}
//		cout << ret << endl;
//	}
//	return 0;
//}

//P3397 地毯问题 简单二维差分模板题
//const int N = 1010;
//int f[N][N];
//int main()
//{
//	int n, m;
//	cin >> n >> m;
//	int x1, y1, x2, y2;
//	for (int i = 1; i <= m; i++)
//	{
//		cin >> x1 >> y1 >> x2 >> y2;
//		f[x1][y1]++;
//		f[x1][y2 + 1]--;
//		f[x2 + 1][y1]--;
//		f[x2 + 1][y2 + 1]++;
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= n; j++)
//		{
//			f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
//			cout << f[i][j] << " ";
//		}
//		cout << endl;
//	}
//	return 0;
// }

//二维差分
//作用：以x1,y1为左上角，x2,y2到右下角的矩阵 统一加上k
//typedef long long int LL;
//const int N = 1010;
//LL f[N][N];
////以x1,y1为左上角，x2,y2到右下角的矩阵 统一加上k
//void insert(int x1,int y1,int x2,int y2,int k)
//{
//	f[x1][y1] += k;
//	f[x2 + 1][y1] -= k;
//	f[x1][y2 + 1] -= k;
//	f[x2 + 1][y2 + 1] += k;
//}
//int main()
//{
//	int n, m, q;
//	cin >> n >> m >> q;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			int x; cin >> x;
//			insert(i, j, i, j, x);//直接用差分数组性质来存
//		}
//	}
//	//执行修改
//	while (q--)
//	{
//		int x1, y1, x2, y2, k;
//		cin >> x1 >> y1 >> x2 >> y2 >> k;
//		insert(x1, y1, x2, y2, k);
//	}
//
//	//在差分数组基础上 通过前缀和复原数组
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
//			cout << f[i][j] << " ";
//		}
//		cout << endl;
//	}
//	return 0;
//}